class Solution {
    // public int minPathSum(int[][] grid) {
    //     // 创建dp表、初始化、填表、返回值
        
    //     int m = grid.length, n = grid[0].length;
    //     int[][] dp = new int[m][n];

    //     // 将 i==0 和 j==0 的位置初始化
    //     dp[0][0] = grid[0][0];
    //     for (int i = 1; i < n; i++) {
    //         dp[0][i] = dp[0][i-1] + grid[0][i];
    //     }
    //     for (int i = 1; i < m; i++) {
    //         dp[i][0] = dp[i-1][0] + grid[i][0];
    //     }

    //     for (int i = 1; i < m; i++) {
    //         for (int j = 1; j < n; j++) {
    //             dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    //         }
    //     }

    //     return dp[m-1][n-1];
    // }



    public int minPathSum(int[][] grid) {
        // 创建dp表、初始化、填表、返回值
        
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m+1][n+1]; // 多加一行与一列

        // 将虚拟行与列都初始化为最大值
        for (int i = 0; i <= n; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        // 将[0,1]和[1,0]初始化为0
        dp[0][1] = dp[1][0] = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }

        return dp[m][n];
    }
}